808F - Card Game - CodeForces Solution

#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

using ll = long long;
using pii = pair<int, int>;

#define F first
#define S second
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
    assert(l <= r);
    return uniform_int_distribution<ll> (l, r)(rng);
}

const ll INF = 1e18;
struct Dinic{
    const static bool SCALING = false; // scaling = EV log(max C) with larger constant
    ll lim = 1;

    struct Edge{
        int u, v;
        ll cap, flow;
    };

    int n, s, t;
    vector<int> level, ptr;
    vector<Edge> e;
    vector<vector<int>> g;

    Dinic(int _n) : n(_n), level(_n), ptr(_n), g(_n){
        e.clear();
        for(int i = 0; i < n; ++i){
            ptr[i] = 0;
            g[i].clear();
        }
    }

    void add_edge(int u, int v, ll c){
        debug(u, v, c);
        g[u].push_back(sz(e));
        e.push_back({u, v, c, 0});
        g[v].push_back(sz(e));
        e.push_back({v, u, 0, 0});
    }

    ll get_max_flow(int _s, int _t){
        s = _s, t = _t;
        ll flow = 0;
        for(lim = SCALING ? (1 << 30) : 1; lim > 0; lim >>= 1){
            while(1){
                if(!bfs()) break;
                fill(all(ptr), 0);
                while(ll pushed = dfs(s, INF))
                    flow += pushed;
            }
        }
        return flow;
    }

private:
    bool bfs(){
        queue<int> q;
        q.push(s);
        fill(all(level), -1);
        level[s] = 0;
        while(!q.empty()){
            int u = q.front();
            q.pop();
            for(int id : g[u]){
                if(e[id].cap - e[id].flow < 1)
                    continue;
                if(level[e[id].v] != -1)
                    continue;
                if(SCALING and e[id].cap - e[id].flow < lim)
                    continue;
                level[e[id].v] = level[u] + 1;
                q.push(e[id].v);
            }
        }
        return level[t] != -1;
    }

    ll dfs(int u, ll flow){
        if(!flow)
            return 0;
        if(u == t)
            return flow;
        for(; ptr[u] < sz(g[u]); ++ptr[u]){
            int id = g[u][ptr[u]], to = e[id].v;
            if(level[to] != level[u] + 1)
                continue;
            ll pushed = dfs(to, min(flow, e[id].cap - e[id].flow));
            if(pushed){
                e[id].flow += pushed;
                e[id ^ 1].flow -= pushed;
                return pushed;
            }
        }
        return 0;
    }
};

const int N = 103;

struct Card{
    int p, c, l;
} card[N];

int n, k;

bool is_prime(ll x){
    if(x <= 1)
        return 0;
    for(ll i = 2; i * i <= x; ++i)
        if(x % i == 0)
            return 0;
    return 1;
}

bool check(int level){
    vector<Card> dak;
    int total = 0;
    int troll = -1;

    for(int i = 1; i <= n; ++i){
        if(card[i].l > level)
            continue;
        if(card[i].c == 1){
            if(troll == -1 or card[troll].p < card[i].p) troll = i;
        }
        else{
            debug(card[i].c);
            dak.push_back(card[i]);
            total += card[i].p;
        }
    }

    if(troll != -1){
        total += card[troll].p;
        dak.push_back(card[troll]);
    }

    Dinic dinic(sz(dak) + 2);
    int st = sz(dak), en = sz(dak) + 1;

    for(int i = 0; i < sz(dak); ++i){
        if(dak[i].c & 1){
            dinic.add_edge(st, i, dak[i].p);
            for(int j = 0; j < sz(dak); ++j){
                if(i == j)
                    continue;
                if(is_prime(dak[i].c + dak[j].c))
                    dinic.add_edge(i, j, INF);
            }
        }
        else
            dinic.add_edge(i, en, dak[i].p);
    }

    int res = total - dinic.get_max_flow(st, en);

    debug(level, res);

    return res >= k;
}

void solve(){
    cin >> n >> k;
    for(int i = 1; i <= n; ++i)
        cin >> card[i].p >> card[i].c >> card[i].l;
    int l = 1, r = n, res = -1;
    while(l <= r){
        int mid = (l + r) / 2;
        if(check(mid)){
            res = mid;
            r = mid - 1;
        }
        else
            l = mid + 1;
    }
    cout << res;
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    #define task "troll"
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int test = 1;
//    cin >> test;
    for(int i = 1; i <= test; ++i){
//        cout << "Case #" << i << ": ";
        solve();
    }
    #ifdef LOCAL
        cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    #endif
    return 0;
}